package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;



import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
	Sort a linked list using insertion sort.
题目大意
	　插入排序           
解题思路
	
 * @Date 2017-10-03 23：51
 */
public class _147_Insertion_Sort_List {
	/**
	 * 直接插入排序
	 * @param head
	 * @return
	 */
	public ListNode insertionSortList(ListNode head) {
		if (head==null)	return null;
		ListNode tHead = new ListNode(-1);
		ListNode pre = tHead, cur = head;
		while (cur != null) {
			ListNode next = cur.next;  
			//直插遍历(从左向右)
			pre = tHead;
			while (pre.next!=null && pre.next.val<=cur.val) 
				pre = pre.next;
			//插入
			cur.next = pre.next;
			pre.next = cur;
			cur = next;
		}
		return tHead.next;
	}
    
	public static void main(String[] args) {
		_147_Insertion_Sort_List obj = new _147_Insertion_Sort_List();

		obj.insertionSortList(null);
	}

}
